package main.leetcode.primary.from001to100;

import java.util.LinkedList;
import java.util.List;

/**
 * 46.全排列
 *
 * <p>给定一个没有重复数字的序列，返回其所有可能的全排列。
 *
 * <p>示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex46 {
    public static void main(String[] args) {
        System.out.println(new ex46().permute(new int[] {1, 2, 3}));
    }

    // 回溯
    //  public List<List<Integer>> permute(int[] nums) {
    //    int n = nums.length;
    //    List<List<Integer>> res = new ArrayList<>();
    //    boolean[] isUsed = new boolean[n]; // 标记是否被使用过（用于状态重置
    //    dfs(nums, n, 0, isUsed, new ArrayList<>(), res);
    //    return res;
    //  }
    //
    //  private void dfs(
    //      int[] nums, int n, int i, boolean[] isUsed, List<Integer> path, List<List<Integer>> res)
    // {
    //    if (i == n) {
    //      res.add(new ArrayList<>(path)); // 拷贝
    //      return;
    //    }
    //    for (int j = 0; j < n; j++) {
    //      if (!isUsed[j]) {
    //        path.add(nums[j]);
    //        isUsed[j] = true;
    //        dfs(nums, n, i + 1, isUsed, path, res); // 放下一个数
    //        isUsed[j] = false; // 状态重置
    //        path.remove(path.size() - 1); // 状态重置
    //      }
    //    }
    //  }

    //    public List<List<Integer>> permute(int[] nums) {
    //        int n = nums.length;
    //        if (n == 0) return new ArrayList<>();
    //        List<List<Integer>> res = new ArrayList<>();
    //        List<Integer> list = new ArrayList<>();
    //        for (int val : nums) list.add(val);
    //        dfs(list, n, 0, res);
    //        return res;
    //    }
    //
    //    private void dfs(List<Integer> nums, int n, int i, List<List<Integer>> res) {
    //        if (i == n) res.add(new ArrayList<>(nums));
    //        for (int j = i; j < n; j++) {
    //            Collections.swap(nums, i, j); // 通过交换来让其他的数做头
    //            dfs(nums, n, i + 1, res);
    //            Collections.swap(nums, i, j); // 状态重置
    //        }
    //    }

    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new LinkedList<>();
        boolean[] isVisited = new boolean[n];
        dfs(nums, isVisited, res, new LinkedList<>());
        return res;
    }

    private void dfs(
            int[] nums, boolean[] isVisited, List<List<Integer>> res, LinkedList<Integer> path) {
        if (path.size() == nums.length) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                path.add(nums[i]);
                dfs(nums, isVisited, res, path);
                isVisited[i] = false;
                path.removeLast();
            }
        }
    }
}
